package com.fw.leetcode;

public enum Label {
    BINARY_SEARCH(Complexity.O_LogN, Complexity.O_1), /* 二分（乘法|除法）：时O(log n) 空O(1) */
    BIT_MAP(Complexity.O_N, Complexity.O_N), /* 位图标记：时O(n) 空O(n) */
    DIRECT_INSERT_SORT(Complexity.O_N2, Complexity.O_1), /* [插入排序] 直接插入排序：时O(n^2) 空O(1) */
    SHELL_INSERT_SORT(Complexity.O_N2, Complexity.O_1),  /* [插入排序] 希尔排序：时O(n^1.5) ~ O(n^2) 空O(1) */
    BUBBLE_SORT(Complexity.O_N2, Complexity.O_1),        /* [交换排序] 冒泡排序：时O(n^2) 空O(1) */
    QUICK_SORT(Complexity.O_N_LogN, Complexity.O_LogN),  /* [交换排序] 快速排序：时O(nlog n) ~ O(n^2) 空O(log n) */
    MERGE_SORT(Complexity.O_N_LogN, Complexity.O_N),     /* [归并排序] 归并排序：时O(nlog n) 空O(n) */
    SELECT_SORT(Complexity.O_N2, Complexity.O_1),        /* [选择排序] 选择排序：时O(n^2) 空O(1) - 选择一个最值放在已排序末尾 */
    HEAP_SORT(Complexity.O_N_LogN, Complexity.O_1),      /* [选择排序] 堆排序：时O(nlog n) 迭代空O(1) 递归空O(log n) - 选择一个最值放在堆尾 */
    ARRAYS_SORT(Complexity.O_N_LogN, Complexity.O_1),    /* Arrays.sort 通用排序：时O(nlog n) 空O(1) */
    ARRAY_INDEX(Complexity.O_N, Complexity.O_N), /* 数组元素建立索引，以便保留排序前元素索引：时O(n) 空O(n) */
    SUM(Complexity.O_N, Complexity.O_1), /* 求和：时O(n) 空O(1) */
    MAX(Complexity.O_N, Complexity.O_1), /* 求最大值：时O(n) 空O(1) */
    DOUBLE_POINTER(Complexity.O_M_N, Complexity.O_LogM_LogN), /* 双指针：时O(m+n) 空O(log m + log n) */
    MATRIX(Complexity.O_MN, Complexity.O_1), /* 矩阵：时O(mn) 空O(1) */
    DIRECTION_VECTOR(Complexity.NONE, Complexity.NONE), /* 方向向量 */
    LAYER(Complexity.NONE, Complexity.NONE), /* 分层 */
    MARK(Complexity.NONE, Complexity.NONE), /* 标记 */
    GREEDY(Complexity.NONE, Complexity.NONE), /* 贪心 */
    DYNAMIC_PROGRAMMING(Complexity.NONE, Complexity.NONE), /* 动态规划（有些可以滚动数组简化） */
    CLIMBING(Complexity.NONE, Complexity.NONE), /* 爬坡 */
    QUEUE(Complexity.NONE, Complexity.NONE), /* 队列 */
    STACK(Complexity.NONE, Complexity.NONE), /* 栈 */
    LINKED_LIST(Complexity.NONE, Complexity.NONE), /* 链表 */
    BINARY_TREE(Complexity.NONE, Complexity.NONE), /* 二叉树 */
    BINARY_SEARCH_TREE(Complexity.NONE, Complexity.NONE), /* 二叉搜索树 */
    DEPTH_FIRST_SEARCH(Complexity.NONE, Complexity.NONE), /* 深度优先搜索(递归|栈) DFS ：时O(n) 空O(log n ~ n) */
    BREADTH_FIRST_SEARCH(Complexity.NONE, Complexity.NONE), /* 广度优先搜索(队列) BFS ：时O(n) 空O(<n)依队列长度，最坏情况O(n) */
    RECURSION(Complexity.NONE, Complexity.NONE), /* 递归 */
    ITERATION(Complexity.NONE, Complexity.NONE), /* 迭代 */
    ENUMERATION(Complexity.NONE, Complexity.NONE), /* 枚举 */
    SLIDING_WINDOW(Complexity.NONE, Complexity.NONE), /* 滑动窗口 */
    HASH_TABLE(Complexity.NONE, Complexity.NONE); /* 哈希表：计算出现频率 */

    private Complexity timeComplexity; /* 算法时间复杂度 */
    private Complexity spaceComplexity; /* 算法空间复杂度 */

    Label(Complexity timeComplexity, Complexity spaceComplexity) {
        this.timeComplexity = timeComplexity;
        this.spaceComplexity = spaceComplexity;
    }

    enum Complexity {
        NONE,
        O_MN, /* O(mn) */
        O_N2, /* O(n^2) */
        O_N_LogN, /* O(nlog n) */
        O_M_N, /* O(m+n) */
        O_LogM_LogN, /* O(log m + log n) */
        O_N, /* O(n) */
        O_LogN, /* O(log n) */
        O_1, /* O(1) */
    }
}
